package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/count-nodes-equal-to-average-of-subtree/description
 * ```
 * 2265. 统计值等于子树平均值的节点数
 * 给你一棵二叉树的根节点 root ，找出并返回满足要求的节点数，要求节点的值等于其 子树 中值的 平均值 。
 *
 * 注意：
 * n 个元素的平均值可以由 n 个元素 求和 然后再除以 n ，并 向下舍入 到最近的整数。
 * root 的 子树 由 root 和它的所有后代组成。
 *
 *
 * 示例 1：
 *
 * 输入：root = [4,8,5,0,1,null,6]
 * 输出：5
 * 解释：
 * 对值为 4 的节点：子树的平均值 (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4 。
 * 对值为 5 的节点：子树的平均值 (5 + 6) / 2 = 11 / 2 = 5 。
 * 对值为 0 的节点：子树的平均值 0 / 1 = 0 。
 * 对值为 1 的节点：子树的平均值 1 / 1 = 1 。
 * 对值为 6 的节点：子树的平均值 6 / 1 = 6 。
 *
 * 示例 2：
 * 输入：root = [1]
 * 输出：1
 * 解释：对值为 1 的节点：子树的平均值 1 / 1 = 1。
 *
 *
 * 提示：
 * 树中节点数目在范围 [1, 1000] 内
 * 0 <= Node.val <= 1000
 * ```
 */
class leetcode_2256 {
    @Test
    fun test_1() {
        val actual = TreeNode(1)
        val expected = 1
        Assert.assertEquals(expected, actual)
    }

    private fun averageOfSubtree(root: TreeNode?): Int {
        /**
        题型：二叉树的后序遍历 + 分治法

        思路：
        遍历时，统计到当前节点时的总和，以及节点数。若当前节点等于平均值，则递增num

        时间复杂度：O（N）

        空间复杂度：O（N）
         */
        collect(root)
        return num
    }

    var num: Int = 0
    private fun collect(root: TreeNode?): Result { // 返回值： 到当前节点时的总和，以及节点数
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (null == root) {
            return Result(0, 0)
        }
        // 3 确定单次递归的处理逻辑：后序遍历
        // 左
        val left: Result = collect(root.left)

        // 右
        val right: Result = collect(root.right)

        // 中
        val sum: Int = left.sum + right.sum + root.`val`
        val count: Int = left.count + right.count + 1
        val aver = sum / count
        if (root.`val` == aver) {
            num = num + 1
        }
        println("${root.`val`} node: $sum / $count =$aver")
        return Result(sum, count)
    }

    private data class Result(val sum: Int, val count: Int)
}